
"""
114. 二叉树展开为链表
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    """
    分解二叉树
    思路：定义flatten函数为：先将左子树拉平，再将右子树拉平，拉平操作位置，后序遍历
    每个函数具体操作，先拉左子树，再拉右子树，再后序遍历位置，
    拉平操作：先将左子树当成右子树，再将原左子树放到新右子树的节点上
    """
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        # 前序位置
        self.flatten(root.left)
        # 中序位置
        self.flatten(root.right)
        # 后序位置
        # 拉平操作
        left = root.left
        right = root.right
        root.right = left
        root.left = None
        tmp = root
        while tmp.right:
            tmp = tmp.right
        tmp.right = right


